#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
}ListNode;

ListNode* partition(ListNode* pHead, int x) {
    // write code here
    struct ListNode* lessGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* greaterGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* lessTail = lessGuard;
    lessGuard->next = NULL;
    greaterGuard->next = NULL;
    struct ListNode* greaterTail = greaterGuard;
    struct ListNode* cur = pHead;
    while (cur)
    {
        if (cur->val >= x)
        {
            greaterTail->next = cur;
            greaterTail = greaterTail->next;
        }
        else
        {
            lessTail->next = cur;
            lessTail = lessTail->next;
        }
        cur = cur->next;
    }
    lessTail->next = greaterGuard->next;
    greaterTail->next = NULL;
    pHead = lessGuard->next;
    free(greaterGuard);
    free(lessGuard);
    return pHead;
}

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1, * n2, * n3;
    n1 = NULL;
    n2 = head;
    n3 = NULL;
    while (n2)
    {
        n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
    }
    return n1;
}
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
bool chkPalindrome(ListNode* A) {
    // write code here
    struct ListNode* mid = middleNode(A);
    struct ListNode* rmid = reverseList(mid);
    struct ListNode* cur = A;
    while (rmid)
    {
        if (cur->val != rmid->val)
        {
            return false;
        }
        rmid = rmid->next;
        cur = cur->next;
    }
    return true;
}